package cn.hy.today;

import java.util.PriorityQueue;

// 移除石子使总数最小
class Solution_1962 {

    // 要求 k 次拿完后，剩下的石头数最少，可以贪心地每次都从石子数最多的堆里拿石头，然后将剩下的放回去。
    // 贪心 + 优先级队列
    public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int pile : piles) {
            pq.offer(pile);
        }
        for (int i = 0; i < k; i++) {
            Integer poll = pq.poll();
            poll -= poll / 2;
            pq.offer(poll);
        }
        int sum = 0;
        while (!pq.isEmpty()) {
            sum += pq.poll();
        }
        return sum;
    }
}